package com.job.microsoft;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author angzhijin
 * @Description
 * @create 2022-08-26 8:23 下午
 */
public class Microsoft0826 {

    public static void main(String[] args) {
//        int res1 = solution1("bdaaadadb");
//        System.out.println(res1);
//        int res2 = solution1("abacb");
//        System.out.println(res2);
//        int res3 = solution1("zthtzh");
//        System.out.println(res3);

        int res21 = solution2(new int[]{-3,-2,1,0,8,7,1}, 3);
        System.out.println(res21);
        int res22 = solution2(new int[]{7,1,11,8,4,10},8);
        System.out.println(res22);


//        int res31 = solution3(new int[]{1,2,4,3}, new int[]{1,3,2,3});
//        System.out.println(res31);
//        int res32 = solution3(new int[]{3,2,1,6,5}, new int[]{4,2,1,3,3});
//        System.out.println(res32);
//        int res33 = solution3(new int[]{1,2}, new int[]{1,2});
//        System.out.println(res33);
    }


    public static int solution1(String S){
        int res =0;
        int[] count = new int[26];
        int len = S.length();
        char[] chars = S.toCharArray();
        for (int c = 1; c <= 26; c++) { // 当前限定字符类型数
            Arrays.fill(count,0);
            // tot为[i，j]间的字符类型数， sum为出现次数为偶数次的字符类型数
            for (int i=0,j = 0, tot=0, sum=0; i < len; i++) {
                int curr = chars[i]-'a';
                count[curr]++;
                if(count[curr]==1) tot++;
                if(count[curr]%2==0)sum++;
                if(count[curr]%2!=0 && count[curr]>1) sum--;

                while(tot > c){
                    int next = chars[j++]-'a';
                    count[next]--;
                    if(count[next]==0) tot--;
                    if(count[next]%2!=0) sum--;
                }
                if(tot==sum)
                    res = Math.max(res, i-j+1);
            }
        }
        return res;
    }

    public static int solution2(int[] A, int M) {
        int N = A.length;
        if(N==0) return 0;
        if(N==1) return 1;
        int res =1;
        int[] visit = new int[N];
        Arrays.sort(A);
        for (int i = 0; i < N; i++) {
            if(visit[i]==1) continue;
            List<Integer> list =new ArrayList<>();
            list.add(A[i]);
            visit[i] = 1;
            int j=i+1;
            int tmp = A[i];
            while (j<N){
                while (A[j]>tmp)
                    tmp+=M;
                if(A[j]==tmp){
                    list.add(A[j]);
                    visit[j] = 1;
                }
                j++;
            }
            res =Math.max(res, list.size());
        }
        return res;
    }

    public static int solution3(int[] A, int[] B){
        int len = A.length;
        int[] C = new int[len+1];
        for (int i = 0; i < len; i++) {
            C[i+1] = Math.max(A[i],B[i]);
        }
        Arrays.sort(C);
        int res =1;
        for (int i = 1; i <= len; i++) {
            if(C[i]!=res && C[i]!=res+1)
                break;
            res = C[i];
        }
        return res+1;
    }
}